The first public-key cryptography scheme was introduced in 1975. Since then, many public-keys schemes have been developed and published. Many public-key schemes require some arithmetic computations modulo an integer n, where today n is typically between 512 and 1024 bits.
Due to the relatively large number of bits n, such public-key schemes are relatively slow in operation and are considered heavy consumers of random-access-memory (RAM) and other computing resources. These problems are particularly acute in applications in which the computing resources are limited, such as smart card applications. Thus, in order to overcome these problems, other families of public-key schemes which do not require many arithmetic computations modulo n have been developed. Among these other families are schemes where the public-key is given as a set of k multivariable polynomial equations over a finite mathematical field K which is relatively small, e.g. between 2 and 264.
The set of k multivariable polynomial equations can be written as follows:y1=P1(xl, . . . , xn)y2=P2(x1, . . . , xn)yk=Pk(x1, . . . , xn),where P1, . . . , PK are multivariable polynomials of small total degree, typically, less than or equal to 8, and in many cases, exactly two.
Examples of such schemes include the C* scheme of T. Matsumoto and H. Imai, the HFE scheme of Jacques Patarin, and the basic form of the “Oil and Vinegar” scheme of Jacques Patarin.
The C* scheme is described in an article titled “Public Quadratic Polynomial-tuples for Efficient Signature Verification and Message-encryption” in Proceedings of EUROCRYPT'88, Springer-Verlag, pp. 419–453. The HFE scheme is described in an article titled “Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms” in Proceedings of EUROCRYPT'96, Springer-Verlag, pp. 33–48. The basic form of the “Oil and Vinegar” scheme of Jacques Patarin is described in an article titled “The Oil and Vinegar Signature Scheme” presented at the Dagstuhl Workshop on Cryptography in September 1997.
In the basic form of the “Oil and Vinegar” scheme computation of a signature x of y is performed as follows:
Step 1: y=(y1, . . . , yn) is transformed into b=(b1, . . . , bn) such that b=t−1(y), where t is the secret, bijective, and affine function from Kn to Kn.
Step 2: We find n variables a1, . . . , an of K, and n variables a′1, . . . , a′n, of K, such that the n equations (S) are satisfied:∀i, 1≦i≦n, bi=Σγijkaja′k+Σλijka′ja′kΣξijka′ja′k+Σξ′ija′jδi.  (S)This can be done as follows: we choose at random the n variables a′i, and then we compute the ai variables from (S) by Gaussian reductions (because—since there are no aiaj terms—the (S) equations are n equations of degree one in the ai variables when the a′i variables are fixed).Step 3: Let A be the element of K2n defined by A=(a1, . . . , an, a′1, . . . , a′n). A is transformed into x such that x=s−1(A), where s is the secret, bijective and affine function from K2n to K2n.
However, the C* scheme and the basic form of the “Oil and Vinegar” scheme have been shown to be insecure in that cryptanalysis of both the C* scheme and the basic form of the “Oil and Vinegar” scheme have been discovered and published by Aviad Kipnis and Adi Shamir in an article titled “Cryptanalysis of the Oil and Vinegar Signature Scheme” in Proceedings of CRYPTO'98, Springer-Verlag LNCS no 1462, pp. 257–266. Weaknesses in construction of the HFE scheme have been described in two unpublished articles titled “Cryptanalysis of the HFE Public Key Cryptosystem” and “Practical Cryptanalysis of the Hidden Fields Equations (HFE)”, but at present, the HFE scheme is not considered compromised since for well chosen and still reasonable parameters, the number of computations required to break the HFE scheme is still too large.
Some aspects of related technologies are described in the following publications:
U.S. Pat. No. 5,263,085 to Shamir describes a new type of digital signature scheme whose security is based on the difficulty of solving systems of k polynomial equations in m unknowns modulo a composite n; and
U.S. Pat. No. 5,375,170 to Shamir describes a novel digital signature scheme which is based on a new class of birational permutations which have small keys and require few arithmetic operations.
The disclosures of all references mentioned above and throughout the present specification are hereby incorporated herein by reference.